﻿using System;
using System.Collections.Generic;
using System.Linq;

namespace Point24.Core
{
    /// <summary>
    /// Author: Shine.Li
    /// Date  : 2021/09/10
    /// 任意1-10中的4个数字，使用加减乘除计算得出24结果的可能组合
    /// </summary>
    public static class Caculator
    {
        /// <summary>
        /// 计算24点中可以到的操作
        /// </summary>
        private static char[] OPERATORS = { '+', '-', '*', '/' };
        /// <summary>
        /// 数字个数
        /// </summary>
        private const int NUMBERSIZE = 4;
        /// <summary>
        /// 期望值
        /// </summary>
        private const int EXPECT = 24;

        /// <summary>
        /// 计算array能算24点的所有组合，从左到右的顺序
        /// </summary>
        /// <param name="array"></param>
        /// <returns></returns>
        public static List<string> Point24(int[] array)
        {
            List<string> expressionList = new List<string>();
            if (array.Length != NUMBERSIZE)
            {
                throw new Exception("不是四个数");
            }
            var allArray = FullPermutation(array);
            Dictionary<int, string> expressionDic = new Dictionary<int, string>();
            foreach (var one in allArray)
            {
                foreach (char op in OPERATORS)
                {
                    double result = GetTwoNumCaculate(one[0], one[1], op);
                    if (!IsInteger(result))
                    {
                        continue;
                    }
                    foreach (char op2 in OPERATORS)
                    {
                        double result1 = GetTwoNumCaculate(result, one[2], op2);
                        if (!IsInteger(result1))
                        {
                            continue;
                        }
                        foreach (char op3 in OPERATORS)
                        {
                            double result2 = GetTwoNumCaculate(result1, one[3], op3);
                            if (result2 == EXPECT)
                            {
                                string expressionStr = $"{GetExpression(one[0], op, one[1], op2, one[2], op3, one[3], expressionDic)}={EXPECT}";
                                if (!expressionList.Contains(expressionStr))
                                {
                                    expressionList.Add(expressionStr);
                                }
                            }
                        }
                    }
                }
            }
            return expressionList;
        }
        /// <summary>
        /// 生成表达式，并做交换律处理
        /// </summary>
        /// <param name="n1"></param>
        /// <param name="op1"></param>
        /// <param name="n2"></param>
        /// <param name="op2"></param>
        /// <param name="n3"></param>
        /// <param name="op3"></param>
        /// <param name="n4"></param>
        /// <param name="expressionDic"></param>
        /// <returns></returns>
        private static string GetExpression(int n1, char op1, int n2, char op2, int n3, char op3, int n4, Dictionary<int, string> expressionDic)
        {
            string expressionStr;
            string expressionStr1;
            int key1 = n1 + op1.GetHashCode() + n2;
            if (!expressionDic.TryGetValue(key1, out expressionStr1))
            {
                expressionStr1 = $"{n1}{op1}{n2}";
                expressionDic.Add(key1, expressionStr1);
            }
            bool isHighOp1 = op1 == '*' || op1 == '/';
            bool isHighOp2 = op2 == '*' || op2 == '/';
            bool isHighOp3 = op3 == '*' || op3 == '/';
            if (!isHighOp1)
            {
                if (!isHighOp2)
                {
                    int key2 = key1 + op2.GetHashCode() + n3;
                    string expressionStr2;
                    if (!expressionDic.TryGetValue(key2, out expressionStr2))
                    {
                        expressionStr2 = $"{expressionStr1}{op2}{n3}";
                        expressionDic.Add(key2, expressionStr2);
                    }
                    if (!isHighOp3)
                    {
                        int key3 = key2 + op2.GetHashCode() + n4;
                        string expressionStr3;
                        if (!expressionDic.TryGetValue(key3, out expressionStr3))
                        {
                            expressionStr3 = $"{expressionStr2}{op3}{n4}";
                            expressionDic.Add(key3, expressionStr3);
                        }
                        expressionStr = expressionStr3;
                    }
                    else
                    {
                        int key3 = "(".GetHashCode() + key2 + ")".GetHashCode() + op2.GetHashCode() + n4;
                        string expressionStr3;
                        if (!expressionDic.TryGetValue(key3, out expressionStr3))
                        {
                            expressionStr3 = $"({expressionStr2}){op3}{n4}";
                            expressionDic.Add(key3, expressionStr3);
                        }
                        expressionStr = expressionStr3;
                    }
                }
                else
                {
                    int key2 = "(".GetHashCode() + key1 + ")".GetHashCode() + op2.GetHashCode() + n3;
                    string expressionStr2;
                    if (!expressionDic.TryGetValue(key2, out expressionStr2))
                    {
                        expressionStr2 = $"({expressionStr1}){op2}{n3}";
                        expressionDic.Add(key2, expressionStr2);
                    }
                    int key3 = key2 + op2.GetHashCode() + n4;
                    string expressionStr3;
                    if (!expressionDic.TryGetValue(key3, out expressionStr3))
                    {
                        expressionStr3 = $"{expressionStr2}{op3}{n4}";
                        expressionDic.Add(key3, expressionStr3);
                    }
                    expressionStr = expressionStr3;
                }
            }
            else
            {
                int key2 = key1 + op2.GetHashCode() + n3;
                string expressionStr2;
                if (!expressionDic.TryGetValue(key2, out expressionStr2))
                {
                    expressionStr2 = $"{expressionStr1}{op2}{n3}";
                    expressionDic.Add(key2, expressionStr2);
                }
                if (!isHighOp2)
                {

                    if (!isHighOp3)
                    {
                        int key3 = key2 + op2.GetHashCode() + n4;
                        string expressionStr3;
                        if (!expressionDic.TryGetValue(key3, out expressionStr3))
                        {
                            expressionStr3 = $"{expressionStr2}{op3}{n4}";
                            expressionDic.Add(key3, expressionStr3);
                        }
                        expressionStr = expressionStr3;
                    }
                    else
                    {
                        int key3 = "(".GetHashCode() + key2 + ")".GetHashCode() + op2.GetHashCode() + n4;
                        string expressionStr3;
                        if (!expressionDic.TryGetValue(key3, out expressionStr3))
                        {
                            expressionStr3 = $"({expressionStr2}){op3}{n4}";
                            expressionDic.Add(key3, expressionStr3);
                        }
                        expressionStr = expressionStr3;
                    }

                }
                else
                {
                    int key3 = key2 + op2.GetHashCode() + n4;
                    string expressionStr3;
                    if (!expressionDic.TryGetValue(key3, out expressionStr3))
                    {
                        expressionStr3 = $"{expressionStr2}{op3}{n4}";
                        expressionDic.Add(key3, expressionStr3);
                    }
                    expressionStr = expressionStr3;
                }
            }
            return expressionStr;
        }

        /// <summary>
        /// 是否为整数
        /// </summary>
        /// <param name="result"></param>
        /// <returns></returns>
        public static bool IsInteger(double result)
        {
            if (result < 1)
            {
                return false;
            }
            return result == Math.Floor(result);
        }
        /// <summary>
        /// 计算两个数结果
        /// </summary>
        /// <param name="v1"></param>
        /// <param name="v2"></param>
        /// <param name="op"></param>
        /// <returns></returns>
        public static double GetTwoNumCaculate(double v1, double v2, char op)
        {
            double result;
            switch (op)
            {
                case '+':
                    result = v1 + v2;
                    break;
                case '-':
                    result = v1 - v2;
                    break;
                case '*':
                    result = v1 * v2;
                    break;
                case '/':
                    result = v1 / v2;
                    break;
                default:
                    result = -1;
                    break;
            }
            return result;
        }

        /// <summary>
        /// 获取array的所有可能排列
        /// </summary>
        /// <param name="allIndice">待排列数组-数组内不可以保护重复数字</param>
        /// <returns></returns>
        public static IEnumerable<IList<int>> PermutationIndice(IEnumerable<int> allIndice)
        {
            IEnumerable<IList<int>> permutation = null;
            for (int i = 0; i < allIndice.Count(); i++)
            { // 每次迭代，求i个索引的排列全集
                if (i == 0)
                {
                    permutation = Enumerable.Select<int, IList<int>>(allIndice, x => new int[] { x });
                }
                else
                {
                    permutation = Enumerable.SelectMany<IList<int>, IList<int>>(permutation,
                    l => Enumerable.Select<int, IList<int>>(allIndice.Except(l), x => new List<int>(l).Concat(new int[] { x }).ToList()));
                }
            }
            return permutation;
        }
        /// <summary>
        /// 获取array的所有可能排列
        /// </summary>
        /// <param name="allIndice">待排列数组</param>
        /// <param name="distict">是否过滤重复数组</param>
        /// <returns></returns>
        public static List<int[]> FullPermutation(IEnumerable<int> allIndice, bool distict = true)
        {
            int[] src = allIndice.ToArray();
            int len = FatorFun(src.Length);
            List<int[]> permutation = new List<int[]>(len);
            List<int[]> list = GetArrayList(src);
            foreach (var one in list)
            {
                for (int i = 1; i <= one.Length - 1; i++)
                {
                    var arrayList = GetSwapArrayList(one, i);
                    if (distict)
                    {
                        foreach (var array in arrayList)
                        {
                            if (!Exists(permutation, array))
                            {
                                permutation.Add(array);
                            }
                        }
                    }
                    else
                    {
                        permutation.AddRange(arrayList);
                    }
                }
            }
            return permutation;
        }
        /// <summary>
        /// N! 阶乘
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static int FatorFun(int n)
        {
            if (n == 0)
                return 1;
            int temp = 1;
            for (int i = 1; i <= n; i++)
            {
                temp = temp * i;
            }
            return temp;
        }
        /// <summary>
        /// 获取基准数组
        /// </summary>
        /// <param name="src"></param>
        /// <returns></returns>
        public static List<int[]> GetArrayList(int[] src)
        {
            List<int[]> list = new List<int[]>();

            List<int> temp = new List<int>(src.Length);
            for (int i = 0; i < src.Count(); i++)
            {
                int[] one;
                if (i == 0)
                {
                    one = src;
                }
                else
                {
                    int offset = i;
                    temp.Clear();
                    for (int j = offset; j < src.Length + offset; j++)
                    {
                        if (j >= src.Length)
                        {
                            temp.Add(src[j - src.Length]);
                        }
                        else
                        {
                            temp.Add(src[j]);
                        }
                    }
                    one = temp.ToArray();
                }
                list.Add(one);
            }
            return list;
        }
        /// <summary>
        /// 获取array下标遇到i的位置左右组合
        /// </summary>
        /// <param name="array"></param>
        /// <param name="i"></param>
        /// <returns></returns>
        public static List<int[]> GetSwapArrayList(int[] array, int i)
        {
            List<int[]> list = new List<int[]>();
            int len = array.Length;
            int[] tempArray = new int[len];
            for (int j = len - 1; j > 1; j--)
            {
                Array.Copy(array, tempArray, len);
                if (!(j == i - 1 && i == len - 1))
                {
                    for (int k = 0; k < i; k++)
                    {
                        int index = j - k;
                        if (index <= 1)
                        {
                            index = len - (2 - index);
                        }
                        int offset = index - 1;
                        int temp;
                        if (index >= len)
                        {
                            index = 2;
                            offset = len - 1;
                        }
                        temp = tempArray[index];
                        if (offset < 0)
                            offset = len + offset;
                        tempArray[index] = tempArray[offset];
                        tempArray[offset] = temp;
                    }
                }
                else
                {

                }
                int[] tempArray2 = new int[len];
                Array.Copy(tempArray, tempArray2, len);
                list.Add(tempArray2);
            }
            return list;
        }
        /// <summary>
        /// array是否存在list中
        /// </summary>
        /// <param name="list"></param>
        /// <param name="array"></param>
        /// <returns></returns>
        public static bool Exists(List<int[]> list, int[] array)
        {
            foreach (var tmpArray in list)
            {
                if (tmpArray[0] == array[0] && tmpArray[1] == array[1] && tmpArray[2] == array[2] && tmpArray[3] == array[3])
                {
                    return true;
                }
            }
            return false;
        }
    }
}
